package org.sample.algorithm.sort;

public class HeapSort {

    public static int[] sort(int[] array) {
        int lastParent = (array.length - 1) >> 1;
        for (int i = lastParent; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }

        for (int i = array.length - 1; i >= 0; i--) {
            int top = array[0];
            array[0] = array[i];
            array[i] = top;
            shiftDown(array, 0, i);
        }
        return array;
    }

    private static void shiftDown(int[] array, int root, int size) {
        int left, right;
        while ((left = (root << 1) + 1) < size) {
            right = left + 1;
            if (right < size && array[right] > array[left])
                left = right;
            if (array[root] < array[left]) {
                int t = array[root];
                array[root] = array[left];
                array[left] = t;
                root = left;
            } else {
                break;
            }
        }
    }
}